<!DOCTYPE html>
<html lang="zh-CN,en,default">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">
  <meta http-equiv="Cache-Control" content="no-transform">
  <meta http-equiv="Cache-Control" content="no-siteapp">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Monda:300,300italic,400,400italic,700,700italic|Lobster Two:300,300italic,400,400italic,700,700italic|Amita:300,300italic,400,400italic,700,700italic|Montserrat:300,300italic,400,400italic,700,700italic|PT Mono:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"dpbirder.gitee.io","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"flat"},"back2top":{"enable":true,"sidebar":true,"scrollpercent":true},"bookmark":{"enable":true,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":true,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

<script>
    (function(d, w, c) {
        w.ChatraID = 'Z8KH5JTPhxGC84tKb';
        var s = d.createElement('script');
        w[c] = w[c] || function() {
            (w[c].q = w[c].q || []).push(arguments);
        };
        s.async = true;
        s.src = 'https://call.chatra.io/chatra.js';
        if (d.head) d.head.appendChild(s);
    })(document, window, 'Chatra');
</script>
  <meta name="description" content="01背包介绍 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。   背包问题整体框图">
<meta property="og:type" content="article">
<meta property="og:title" content="01背包相关问题">
<meta property="og:url" content="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/index.html">
<meta property="og:site_name" content="dpBirder&#39;s Blog">
<meta property="og:description" content="01背包介绍 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。   背包问题整体框图">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://code-thinking-1253855093.file.myqcloud.com/pics/20210117175428387.jpg">
<meta property="og:image" content="https://code-thinking-1253855093.file.myqcloud.com/pics/20210117171307407.png">
<meta property="og:image" content="https://code-thinking-1253855093.file.myqcloud.com/pics/2021011010304192.png">
<meta property="og:image" content="https://code-thinking-1253855093.file.myqcloud.com/pics/20210110103109140.png">
<meta property="og:image" content="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230729164555543.png">
<meta property="og:image" content="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230804164416041.png">
<meta property="og:image" content="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230804165751885.png">
<meta property="og:image" content="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230804174653790.png">
<meta property="article:published_time" content="2023-07-28T13:54:27.000Z">
<meta property="article:modified_time" content="2023-08-16T12:34:33.515Z">
<meta property="article:author" content="dpbirder">
<meta property="article:tag" content="个人技术博客">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://code-thinking-1253855093.file.myqcloud.com/pics/20210117175428387.jpg">

<link rel="canonical" href="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>
<script> 
 (function(){
        if(''){
            if (prompt('请输入文章密码') !== ''){
                alert('密码错误！');
                history.back();
            }
        }
    })();
</script>
  <title>01背包相关问题 | dpBirder's Blog</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">dpBirder's Blog</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签<span class="badge">15</span></a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类<span class="badge">26</span></a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档<span class="badge">51</span></a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="reading-progress-bar"></div>
  <a role="button" class="book-mark-link book-mark-link-fixed"></a>

  <a href="https://github.com/zhengzp2019" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://dpbirder.gitee.io/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/boy.jpg">
      <meta itemprop="name" content="dpbirder">
      <meta itemprop="description" content="目前研一就读于西安电子科技大学">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="dpBirder's Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          01背包相关问题
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2023-07-28 21:54:27" itemprop="dateCreated datePublished" datetime="2023-07-28T21:54:27+08:00">2023-07-28</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2023-08-16 20:34:33" itemprop="dateModified" datetime="2023-08-16T20:34:33+08:00">2023-08-16</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
                </span>
                  ，
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" itemprop="url" rel="index"><span itemprop="name">动态规划</span></a>
                </span>
            </span>

          <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>7.7k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>7 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h2 id="01背包介绍"><a class="markdownIt-Anchor" href="#01背包介绍"></a> 01背包介绍</h2>
<p>有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。<strong>每件物品只能用一次</strong>，求解将哪些物品装入背包里物品价值总和最大。</p>
<p><img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20210117175428387.jpg" alt="动态规划-背包问题"></p>
<h3 id="背包问题整体框图"><a class="markdownIt-Anchor" href="#背包问题整体框图"></a> 背包问题整体框图</h3>
<p><img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20210117171307407.png" alt="416.分割等和子集1"></p>
<a id="more"></a>
<h3 id="二维数组实现01背包"><a class="markdownIt-Anchor" href="#二维数组实现01背包"></a> 二维数组实现01背包</h3>
<p>考虑动规五部曲</p>
<h4 id="1-状态表示确定dp数组的含义"><a class="markdownIt-Anchor" href="#1-状态表示确定dp数组的含义"></a> 1、状态表示，确定dp数组的含义</h4>
<p>对于背包问题，有一种写法, 是使用二维数组，即<strong>dp[i,j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少</strong>。</p>
<h4 id="2-状态转移确定递推方程"><a class="markdownIt-Anchor" href="#2-状态转移确定递推方程"></a> 2、状态转移，确定递推方程</h4>
<p>状态dp[i,j]由是否选择i转移而来</p>
<ul>
<li>不选i，则dp[i,j] = dp[i-1,j]</li>
<li>选i，则dp[i,j] = dp[i-1, j-weight[i]] + value[i]</li>
</ul>
<p>则状态转移方程为：dp[i,j] = max(dp[i-1. j], dp[i-1, j-weight[i]] + value[i])</p>
<h4 id="3-dp数组初始化"><a class="markdownIt-Anchor" href="#3-dp数组初始化"></a> 3、dp数组初始化</h4>
<p>如下图所示，结合状态转移方程，每个状态都是由上面的状态和左上的状态转移而来，所以实现需要初始化第一行和第一列。</p>
<p>第一行表达的意义是背包容量为0时的最大价值，此时不论可选物品有多少，最大价值都是0；第一列表达的意义是，背包容量为j时，把物品0放入背包的最大价值为多少，此时只有当背包容量大于物品0的重量时，最大价值为物品0的价值，其余为0。</p>
<p><img src="https://code-thinking-1253855093.file.myqcloud.com/pics/2021011010304192.png" alt="动态规划-背包问题2"></p>
<h4 id="4-循环顺序"><a class="markdownIt-Anchor" href="#4-循环顺序"></a> 4、循环顺序</h4>
<p>对于二维数组的01背包问题往往两重循环，一重循环枚举物品，一重循环枚举背包容量，考虑每个状态的转移方式，先枚举物品和先枚举背包容量的方式都可以</p>
<h4 id="5-举例验证"><a class="markdownIt-Anchor" href="#5-举例验证"></a> 5、举例验证</h4>
<p><img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20210110103109140.png" alt="动态规划-背包问题7"></p>
<h3 id="滚动一维数组实现01背包"><a class="markdownIt-Anchor" href="#滚动一维数组实现01背包"></a> 滚动(一维)数组实现01背包</h3>
<h4 id="1-状态表示确定dp数组的含义-2"><a class="markdownIt-Anchor" href="#1-状态表示确定dp数组的含义-2"></a> 1、状态表示，确定dp数组的含义</h4>
<p>dp[j]: 表示背包容量为j时的最大价值</p>
<h4 id="2-状态转移确定递推方程-2"><a class="markdownIt-Anchor" href="#2-状态转移确定递推方程-2"></a> 2、状态转移，确定递推方程</h4>
<p>由二维数组的方法中可以看出，每个i行的状态都是由上一行状态转移过来的，所以可以使用一维数组滚动，每次将更新前的一维数组作为上一行状态，更新后的一维数组作为当前行的状态</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 等式右边的作为当前状态，等式左边的作为上一状态</span></span><br><span class="line">dp[j] = max(dp[j], dp[j-weights[i]]) + values[i]);</span><br></pre></td></tr></table></figure>
<h4 id="3-dp数组初始化-2"><a class="markdownIt-Anchor" href="#3-dp数组初始化-2"></a> 3、dp数组初始化</h4>
<p>dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。</p>
<p>那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？</p>
<p>看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);</p>
<p>dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。</p>
<p><strong>这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了</strong>。</p>
<h4 id="4-遍历顺序"><a class="markdownIt-Anchor" href="#4-遍历顺序"></a> 4、遍历顺序</h4>
<p>只能先遍历物品，在遍历背包容量，且在遍历背包容量的时候要从后向前遍历，为了保证每个物品只能添加一次</p>
<h2 id="01背包相关问题"><a class="markdownIt-Anchor" href="#01背包相关问题"></a> 01背包相关问题</h2>
<table>
<thead>
<tr>
<th>题目</th>
<th>题解</th>
</tr>
</thead>
<tbody>
<tr>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/partition-equal-subset-sum/">416. 分割等和子集</a></td>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/partition-equal-subset-sum/solutions/2363837/san-chong-fang-fa-jie-jue-wen-ti-hui-su-9a6zt/">https://leetcode.cn/problems/partition-equal-subset-sum/solutions/2363837/san-chong-fang-fa-jie-jue-wen-ti-hui-su-9a6zt/</a></td>
</tr>
<tr>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/last-stone-weight-ii/">1049.最后一块石头的重量II</a></td>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/target-sum/solutions/2373127/01bei-bao-shi-jian-fu-za-du-onm-by-dpbir-sxd0/">https://leetcode.cn/problems/target-sum/solutions/2373127/01bei-bao-shi-jian-fu-za-du-onm-by-dpbir-sxd0/</a></td>
</tr>
<tr>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/target-sum/">494.目标和</a></td>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/target-sum/solutions/2373127/01bei-bao-shi-jian-fu-za-du-onm-by-dpbir-sxd0/">https://leetcode.cn/problems/target-sum/solutions/2373127/01bei-bao-shi-jian-fu-za-du-onm-by-dpbir-sxd0/</a></td>
</tr>
<tr>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/ones-and-zeroes/">474.一和零</a></td>
<td><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/ones-and-zeroes/solutions/2377351/er-wei-dong-tai-gui-hua-by-dpbirder-wmt4/">https://leetcode.cn/problems/ones-and-zeroes/solutions/2377351/er-wei-dong-tai-gui-hua-by-dpbirder-wmt4/</a></td>
</tr>
</tbody>
</table>
<h2 id="416分割等和子集"><a class="markdownIt-Anchor" href="#416分割等和子集"></a> 416.分割等和子集</h2>
<h3 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h3>
<p><img src="/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230729164555543.png" alt="image-20230729164555543"></p>
<h3 id="我的思路"><a class="markdownIt-Anchor" href="#我的思路"></a> 我的思路</h3>
<p>计算出集合的总和，原问题可转化为<strong>能否从nums中选择一个子集和为sum/2</strong></p>
<h4 id="回溯法"><a class="markdownIt-Anchor" href="#回溯法"></a> 回溯法</h4>
<h4 id="画出状态树利用回溯三部曲分析问题结果超时"><a class="markdownIt-Anchor" href="#画出状态树利用回溯三部曲分析问题结果超时"></a> 画出状态树，利用回溯三部曲分析问题，结果超时</h4>
<h4 id="递归法"><a class="markdownIt-Anchor" href="#递归法"></a> 递归法</h4>
<p>对于集合中每个元素都只有两种状态，选或不选，分别讨论这两种状态，最终的到一个二叉树</p>
<p>时间复杂度为O(2<sup>N</sup>)，超时</p>
<h4 id="动态规划法"><a class="markdownIt-Anchor" href="#动态规划法"></a> 动态规划法</h4>
<p>将本题对应到背包问题</p>
<ul>
<li>背包容量大小：sum/2</li>
<li>背包中要放入的商品(集合里的元素)，重量为元素值，价值也为元素的值</li>
<li>背包刚好装满，说明找到了总和为sum/2的值</li>
<li>背包中每一个元素不可重复放入</li>
</ul>
<p>所以本题应该套用01背包框架</p>
<p>见代码注释</p>
<h3 id="我的代码"><a class="markdownIt-Anchor" href="#我的代码"></a> 我的代码</h3>
<p><strong>回溯法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 回溯</span></span><br><span class="line">    <span class="function"><span class="keyword">boolean</span> <span class="title">backtracing</span><span class="params">(<span class="keyword">int</span> sum, <span class="keyword">int</span> begin, <span class="keyword">int</span> nums[])</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 终止条件</span></span><br><span class="line">        <span class="keyword">if</span> (sum == <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (sum &lt; <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="comment">// 单层逻辑</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = begin; i &lt; nums.length; i++) &#123;</span><br><span class="line">            <span class="comment">// 同一层去重</span></span><br><span class="line">            <span class="keyword">if</span> (i != begin &amp;&amp; nums[i] == nums[i - <span class="number">1</span>])</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            <span class="comment">// 这里只要判断是否存在，而不需要返回路径，所以不需要一个vec向量来保存路径</span></span><br><span class="line">            <span class="keyword">if</span> (backtracing(sum - nums[i], i + <span class="number">1</span>, nums))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 求和</span></span><br><span class="line">        Arrays.sort(nums);</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> n = nums.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">            sum += nums[i];</span><br><span class="line">        <span class="keyword">if</span> (sum % <span class="number">2</span> != <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        System.out.println(Arrays.toString(nums));</span><br><span class="line">        <span class="comment">// 问题转化：能否从nums中选择一个子集和为sum/2</span></span><br><span class="line">        <span class="keyword">return</span> backtracing(sum / <span class="number">2</span>, <span class="number">0</span>, nums);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>递归法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 递归, 判断集合[id,nums.length]是否存在和为sum的子集</span></span><br><span class="line">    <span class="function"><span class="keyword">boolean</span> <span class="title">recursion</span><span class="params">(<span class="keyword">int</span> nums[], <span class="keyword">int</span> sum, <span class="keyword">int</span> id)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 终止条件</span></span><br><span class="line">        <span class="keyword">if</span> (sum == <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (sum &lt; <span class="number">0</span> || id == nums.length)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="comment">// 递归逻辑</span></span><br><span class="line">        <span class="keyword">return</span> recursion(nums, sum - nums[id], id + <span class="number">1</span>) || recursion(nums, sum, id + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 求和</span></span><br><span class="line">        Arrays.sort(nums);</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> n = nums.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">            sum += nums[i];</span><br><span class="line">        <span class="keyword">if</span> (sum % <span class="number">2</span> != <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="comment">// System.out.println(Arrays.toString(nums));</span></span><br><span class="line">        <span class="comment">// 问题转化：能否从nums中选择一个子集和为sum/2</span></span><br><span class="line">        <span class="keyword">return</span> recursion(nums, sum / <span class="number">2</span>, <span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>01背包——二维数组解法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 动态规划</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 求和</span></span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> n = nums.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">            sum += nums[i];</span><br><span class="line">        <span class="keyword">if</span> (sum % <span class="number">2</span> != <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="comment">// 问题转化：能否从nums中选择一个子集和为sum/2</span></span><br><span class="line">        <span class="comment">// 状态定义：dp[i][j]: 能否从[0~i]中找出和为j的子集</span></span><br><span class="line">        <span class="keyword">boolean</span>[][] dp = <span class="keyword">new</span> <span class="keyword">boolean</span>[nums.length + <span class="number">5</span>][sum / <span class="number">2</span> + <span class="number">5</span>];</span><br><span class="line">        <span class="comment">// 递推方程: dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]</span></span><br><span class="line">        <span class="comment">// 前者表示这样的子集中不含元素i，后者表示这样的子集中包含元素i</span></span><br><span class="line">        <span class="comment">// 初始化，第一列全为true，第一行，若nums[0] == j，则为true，反之false</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= sum / <span class="number">2</span>; j++)</span><br><span class="line">            dp[<span class="number">0</span>][j] = (nums[<span class="number">0</span>] == j);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++)</span><br><span class="line">            dp[i][<span class="number">0</span>] = <span class="keyword">true</span>;</span><br><span class="line">        <span class="comment">// print(dp);</span></span><br><span class="line">        <span class="comment">// 循环过程，两种都可以</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= sum / <span class="number">2</span>; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (j &gt;= nums[i])</span><br><span class="line">                    dp[i][j] = dp[i - <span class="number">1</span>][j] || dp[i - <span class="number">1</span>][j - nums[i]];</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    dp[i][j] = dp[i - <span class="number">1</span>][j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// print(dp);</span></span><br><span class="line">        <span class="keyword">return</span> dp[nums.length - <span class="number">1</span>][sum / <span class="number">2</span>];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// debug</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(<span class="keyword">boolean</span> nums[][])</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">            System.out.println(Arrays.toString(nums[i]));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>01背包——一维数组解法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 01背包——一维数组</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">canPartition</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 求和</span></span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> n = nums.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">            sum += nums[i];</span><br><span class="line">        <span class="keyword">if</span> (sum % <span class="number">2</span> != <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="comment">// 问题转化：能否从nums中选择一个子集和为sum/2</span></span><br><span class="line">        <span class="comment">// 状态表示dp[j]: 容量为j的背包能装物品的最大价值</span></span><br><span class="line">        <span class="keyword">int</span> dp[] = <span class="keyword">new</span> <span class="keyword">int</span>[sum / <span class="number">2</span> + <span class="number">1</span>];</span><br><span class="line">        <span class="comment">// 递推公式：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])</span></span><br><span class="line">        <span class="comment">// 循环顺序</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = sum / <span class="number">2</span>; j &gt;= nums[i]; j--) &#123;</span><br><span class="line">                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> dp[sum / <span class="number">2</span>] == sum / <span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="1049最后一块石头的重量ii"><a class="markdownIt-Anchor" href="#1049最后一块石头的重量ii"></a> 1049.最后一块石头的重量II</h2>
<h3 id="题目描述-2"><a class="markdownIt-Anchor" href="#题目描述-2"></a> 题目描述</h3>
<p><img src="/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230804164416041.png" alt="image-20230804164416041"></p>
<h3 id="我的思路-2"><a class="markdownIt-Anchor" href="#我的思路-2"></a> 我的思路</h3>
<p>将本题转化为背包问题，记石头重量总和为sum，原问题可描述为bag = sum/2的背包所装的石头的最大重量，与剩余石头重量抵消后的剩余石头重量</p>
<ul>
<li>背包容量为 bag</li>
<li>背包中的物品（石头），价值为石头的重量，重量为石头的重量</li>
<li>背包中每个物品只能取一次</li>
</ul>
<p>则该问题为01背包问题，下面用01背包的模板即可</p>
<h3 id="我的代码-2"><a class="markdownIt-Anchor" href="#我的代码-2"></a> 我的代码</h3>
<p>01背包——二维数组版</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lastStoneWeightII</span><span class="params">(<span class="keyword">int</span>[] stones)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; stones.length; i++)</span><br><span class="line">            sum += stones[i];</span><br><span class="line">        <span class="comment">// dp[i][j]: 对于物品[0~i]中背包容量为j时所能装的最大物品价值</span></span><br><span class="line">        <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[stones.length][sum / <span class="number">2</span> + <span class="number">1</span>];</span><br><span class="line">        <span class="comment">// 递推方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i])</span></span><br><span class="line">        <span class="comment">// 前者表示不包含元素i，后者表示包含元素i</span></span><br><span class="line">        <span class="comment">// 初始化</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = stones[<span class="number">0</span>]; j &lt; dp[<span class="number">0</span>].length; j++)</span><br><span class="line">            dp[<span class="number">0</span>][j] = stones[<span class="number">0</span>];</span><br><span class="line">        <span class="comment">// 遍历顺序： 从前向后</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; stones.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; dp[i].length; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (j &lt; stones[i])</span><br><span class="line">                    dp[i][j] = dp[i - <span class="number">1</span>][j];</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    dp[i][j] = Math.max(dp[i - <span class="number">1</span>][j], dp[i - <span class="number">1</span>][j - stones[i]] + stones[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sum - dp[stones.length - <span class="number">1</span>][sum / <span class="number">2</span>] - dp[stones.length - <span class="number">1</span>][sum / <span class="number">2</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>01背包——一维数组版</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lastStoneWeightII</span><span class="params">(<span class="keyword">int</span>[] stones)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> stone : stones)</span><br><span class="line">            sum += stone;</span><br><span class="line">        <span class="keyword">int</span> bag = sum / <span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// dp[j]: 容量为j的背包所能装物品的最大价值</span></span><br><span class="line">        <span class="keyword">int</span> dp[] = <span class="keyword">new</span> <span class="keyword">int</span>[bag + <span class="number">1</span>];</span><br><span class="line">        <span class="comment">// 递推公式：dp[j] = max(dp[j], dp[j-stones[i]] + stones[j])</span></span><br><span class="line">        <span class="comment">// 初始化 省略</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; stones.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = bag; j &gt;= stones[i]; j--)</span><br><span class="line">                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> sum - dp[bag] - dp[bag];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="494目标和"><a class="markdownIt-Anchor" href="#494目标和"></a> 494.目标和</h2>
<h3 id="题目描述-3"><a class="markdownIt-Anchor" href="#题目描述-3"></a> 题目描述</h3>
<p><img src="/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230804165751885.png" alt="image-20230804165751885"></p>
<h3 id="我的思路-3"><a class="markdownIt-Anchor" href="#我的思路-3"></a> 我的思路</h3>
<p>将本题转化为背包问题，根据题意集合一定可以分为left和right两部分，而</p>
<p>left+right=sum，要是left-right=target，只需使left = (sum + target)/2</p>
<p>则原问题可以转化为从集合nums中选择若干个数使其和为left，可以直接使用回溯法解决问题，只不过会超时，这里将其转化为背包问题，转换方法与<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/partition-equal-subset-sum/">416. 分割等和子集</a>类似</p>
<ul>
<li>背包容量：left</li>
<li>背包中的物品（nums中的元素），物品价值为元素大小，物品体积为元素大小</li>
<li>背包中每个物品只能选取一次</li>
</ul>
<p>转换后可解释为：装满容量为left的背包有多少种装法，<strong>这里需要使用01背包的方法解决组合问题</strong></p>
<ol>
<li>
<p>状态定义</p>
<p>dp[j]: 容量为j的背包有dp[j]种组合方法</p>
</li>
<li>
<p>递推方程</p>
<p>例如：dp[j]，j 为5，</p>
<ul>
<li>已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。</li>
<li>已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。</li>
<li>已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包</li>
<li>已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包</li>
<li>已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包</li>
</ul>
<p>那么凑整dp[5]就是把所有的dp[j - nums[i]]累加起来</p>
<p>所以求组合问题的公式，都是类似这种</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 组合问题的递推公式都是这个</span></span><br><span class="line">dp[j] += dp[j-nums[i]]</span><br></pre></td></tr></table></figure>
</li>
<li>
<p>初始化</p>
<p>dp[0] = 1，从满足答案要求判断如何初始化</p>
</li>
<li>
<p>循环方向</p>
<p>物品循环从前向后，背包容量循环从后向前</p>
</li>
</ol>
<h3 id="我的代码-3"><a class="markdownIt-Anchor" href="#我的代码-3"></a> 我的代码</h3>
<p><strong>01背包——一维数组版</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTargetSumWays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 计算背包容量</span></span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> num : nums)</span><br><span class="line">            sum += num;</span><br><span class="line">        <span class="comment">// bag不存在</span></span><br><span class="line">        <span class="keyword">if</span> ((sum + target) % <span class="number">2</span> == <span class="number">1</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="comment">// 问题无解</span></span><br><span class="line">        <span class="keyword">if</span> (Math.abs(target) &gt; sum)</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> bag = (sum + target) / <span class="number">2</span>;</span><br><span class="line">        <span class="comment">// dp[j]: 装满容量为j的背包有多少种装法</span></span><br><span class="line">        <span class="keyword">int</span> dp[] = <span class="keyword">new</span> <span class="keyword">int</span>[bag + <span class="number">1</span>];</span><br><span class="line">        dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = bag; j &gt;= nums[i]; j--)</span><br><span class="line">                dp[j] += dp[j - nums[i]];</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> dp[bag];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="474一和零"><a class="markdownIt-Anchor" href="#474一和零"></a> 474.一和零</h2>
<h3 id="题目描述-4"><a class="markdownIt-Anchor" href="#题目描述-4"></a> 题目描述</h3>
<p><img src="/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/image-20230804174653790.png" alt="image-20230804174653790"></p>
<h3 id="我的思路-4"><a class="markdownIt-Anchor" href="#我的思路-4"></a> 我的思路</h3>
<p>只不过这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。下面考虑动规五部曲</p>
<p>1、状态定义</p>
<p>dp[i,j]: 子集中最多有i个0和j个1的子集长度</p>
<p>2、递推公式</p>
<p>对于字符串str，str中0的次数为zero_times,1的次数为one_times，递推公式如下：</p>
<p>dp[i,j] = max(dp[i - zero_times, j - one_times]，dp[i,j]) + 1</p>
<p>3、初始化</p>
<p>dp[i,j]不为负即可</p>
<p>4、确定遍历顺序</p>
<p>外层循环遍历物品，内层循环遍历背包容量</p>
<p>5、模拟，省略</p>
<h3 id="我的代码-4"><a class="markdownIt-Anchor" href="#我的代码-4"></a> 我的代码</h3>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMaxForm</span><span class="params">(String[] strs, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// dp[i][j]: 最多i个0和j个1的strs的最大子集的大小为dp[i][j]</span></span><br><span class="line">        <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m + <span class="number">1</span>][n + <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">for</span> (String str : strs) &#123;</span><br><span class="line">            <span class="keyword">char</span>[] s_char = str.toCharArray();</span><br><span class="line">            <span class="keyword">int</span> one_num = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">char</span> ch : s_char) &#123;</span><br><span class="line">                <span class="keyword">if</span> (ch == <span class="string">&#x27;1&#x27;</span>)</span><br><span class="line">                    one_num++;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">int</span> zero_num = s_char.length - one_num;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = m; i &gt;= zero_num; i--) &#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j = n; j &gt;= one_num; j--)</span><br><span class="line">                    dp[i][j] = Math.max(dp[i][j], dp[i - zero_num][j - one_num] + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> dp[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

    </div>

    
    
    <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
    
</div>

      <footer class="post-footer">

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2023/07/26/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/" rel="prev" title="动态规划相关问题">
      <i class="fa fa-chevron-left"></i> 动态规划相关问题
    </a></div>
      <div class="post-nav-item">
    <a href="/2023/08/16/%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/" rel="next" title="完全背包相关问题">
      完全背包相关问题 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#01%E8%83%8C%E5%8C%85%E4%BB%8B%E7%BB%8D"><span class="nav-text"> 01背包介绍</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E6%95%B4%E4%BD%93%E6%A1%86%E5%9B%BE"><span class="nav-text"> 背包问题整体框图</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B001%E8%83%8C%E5%8C%85"><span class="nav-text"> 二维数组实现01背包</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-%E7%8A%B6%E6%80%81%E8%A1%A8%E7%A4%BA%E7%A1%AE%E5%AE%9Adp%E6%95%B0%E7%BB%84%E7%9A%84%E5%90%AB%E4%B9%89"><span class="nav-text"> 1、状态表示，确定dp数组的含义</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E7%A1%AE%E5%AE%9A%E9%80%92%E6%8E%A8%E6%96%B9%E7%A8%8B"><span class="nav-text"> 2、状态转移，确定递推方程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#3-dp%E6%95%B0%E7%BB%84%E5%88%9D%E5%A7%8B%E5%8C%96"><span class="nav-text"> 3、dp数组初始化</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-%E5%BE%AA%E7%8E%AF%E9%A1%BA%E5%BA%8F"><span class="nav-text"> 4、循环顺序</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#5-%E4%B8%BE%E4%BE%8B%E9%AA%8C%E8%AF%81"><span class="nav-text"> 5、举例验证</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%BB%9A%E5%8A%A8%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B001%E8%83%8C%E5%8C%85"><span class="nav-text"> 滚动(一维)数组实现01背包</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-%E7%8A%B6%E6%80%81%E8%A1%A8%E7%A4%BA%E7%A1%AE%E5%AE%9Adp%E6%95%B0%E7%BB%84%E7%9A%84%E5%90%AB%E4%B9%89-2"><span class="nav-text"> 1、状态表示，确定dp数组的含义</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E7%A1%AE%E5%AE%9A%E9%80%92%E6%8E%A8%E6%96%B9%E7%A8%8B-2"><span class="nav-text"> 2、状态转移，确定递推方程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#3-dp%E6%95%B0%E7%BB%84%E5%88%9D%E5%A7%8B%E5%8C%96-2"><span class="nav-text"> 3、dp数组初始化</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-%E9%81%8D%E5%8E%86%E9%A1%BA%E5%BA%8F"><span class="nav-text"> 4、遍历顺序</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98"><span class="nav-text"> 01背包相关问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#416%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86"><span class="nav-text"> 416.分割等和子集</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text"> 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E6%80%9D%E8%B7%AF"><span class="nav-text"> 我的思路</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%9B%9E%E6%BA%AF%E6%B3%95"><span class="nav-text"> 回溯法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%94%BB%E5%87%BA%E7%8A%B6%E6%80%81%E6%A0%91%E5%88%A9%E7%94%A8%E5%9B%9E%E6%BA%AF%E4%B8%89%E9%83%A8%E6%9B%B2%E5%88%86%E6%9E%90%E9%97%AE%E9%A2%98%E7%BB%93%E6%9E%9C%E8%B6%85%E6%97%B6"><span class="nav-text"> 画出状态树，利用回溯三部曲分析问题，结果超时</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%80%92%E5%BD%92%E6%B3%95"><span class="nav-text"> 递归法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%B3%95"><span class="nav-text"> 动态规划法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E4%BB%A3%E7%A0%81"><span class="nav-text"> 我的代码</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1049%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8Fii"><span class="nav-text"> 1049.最后一块石头的重量II</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-2"><span class="nav-text"> 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E6%80%9D%E8%B7%AF-2"><span class="nav-text"> 我的思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E4%BB%A3%E7%A0%81-2"><span class="nav-text"> 我的代码</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#494%E7%9B%AE%E6%A0%87%E5%92%8C"><span class="nav-text"> 494.目标和</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-3"><span class="nav-text"> 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E6%80%9D%E8%B7%AF-3"><span class="nav-text"> 我的思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E4%BB%A3%E7%A0%81-3"><span class="nav-text"> 我的代码</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#474%E4%B8%80%E5%92%8C%E9%9B%B6"><span class="nav-text"> 474.一和零</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-4"><span class="nav-text"> 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E6%80%9D%E8%B7%AF-4"><span class="nav-text"> 我的思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%88%91%E7%9A%84%E4%BB%A3%E7%A0%81-4"><span class="nav-text"> 我的代码</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="dpbirder"
      src="/images/boy.jpg">
  <p class="site-author-name" itemprop="name">dpbirder</p>
  <div class="site-description" itemprop="description">目前研一就读于西安电子科技大学</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">51</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">26</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">15</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="sidebar-button motion-element">
    <a onclick="Chatra('openChat', true);"><i class="fa fa-comment"></i>
    Chat
  </a>
  </div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/zhengzp2019" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;zhengzp2019" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://mail.qq.com/" title="E-Mail → https:&#x2F;&#x2F;mail.qq.com&#x2F;" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>



      </div>
        <div class="back-to-top motion-element">
          <i class="fa fa-arrow-up"></i>
          <span>0%</span>
        </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        
  <div class="languages">
    <label class="lang-select-label">
      <i class="fa fa-language"></i>
      <span>简体中文</span>
      <i class="fa fa-angle-up" aria-hidden="true"></i>
    </label>
    <select class="lang-select" data-canonical="">
      
        <option value="zh-CN" data-href="/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/" selected="">
          简体中文
        </option>
      
        <option value="en" data-href="/en/2023/07/28/01%E8%83%8C%E5%8C%85%E7%9B%B8%E5%85%B3%E9%97%AE%E9%A2%98/" selected="">
          English
        </option>
      
    </select>
  </div>

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2024</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">dpbirder</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-area"></i>
    </span>
    <span title="站点总字数">225k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">3:25</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>

<script src="/js/bookmark.js"></script>


  <script defer src="/lib/three/three.min.js"></script>
    <script defer src="/lib/three/three-waves.min.js"></script>


  
  <script>
    (function(){
      var canonicalURL, curProtocol;
      //Get the <link> tag
      var x=document.getElementsByTagName("link");
		//Find the last canonical URL
		if(x.length > 0){
			for (i=0;i<x.length;i++){
				if(x[i].rel.toLowerCase() == 'canonical' && x[i].href){
					canonicalURL=x[i].href;
				}
			}
		}
    //Get protocol
	    if (!canonicalURL){
	    	curProtocol = window.location.protocol.split(':')[0];
	    }
	    else{
	    	curProtocol = canonicalURL.split(':')[0];
	    }
      //Get current URL if the canonical URL does not exist
	    if (!canonicalURL) canonicalURL = window.location.href;
	    //Assign script content. Replace current URL with the canonical URL
      !function(){var e=/([http|https]:\/\/[a-zA-Z0-9\_\.]+\.baidu\.com)/gi,r=canonicalURL,t=document.referrer;if(!e.test(r)){var n=(String(curProtocol).toLowerCase() === 'https')?"https://sp0.baidu.com/9_Q4simg2RQJ8t7jm9iCKT-xh_/s.gif":"//api.share.baidu.com/s.gif";t?(n+="?r="+encodeURIComponent(document.referrer),r&&(n+="&l="+r)):r&&(n+="?l="+r);var i=new Image;i.src=n}}(window);})();
  </script>




  
<script src="/js/local-search.js"></script>




  <script>
    (function(d, w, c) {
      w.ChatraID = 'Z8KH5JTPhxGC84tKb';
      var s = d.createElement('script');
      w[c] = w[c] || function() {
        (w[c].q = w[c].q || []).push(arguments);
      };
      s.async = true;
      s.src = 'https://call.chatra.io/chatra.js';
      if (d.head) d.head.appendChild(s);
    })(document, window, 'Chatra');
  </script>









  

  

  

</body>
</html>
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/love.js"></script>
